package algorithms;

import environment.environment;
import settings.Settings;

import java.util.ArrayList;

public class Djikstra implements FindPath {
	
	int [][] map;
	int x,y;
	
	ArrayList<Integer> ML; 
	
	public Djikstra(environment E, int X, int Y){
		
		this.map = E.GUI;
		this.x = X;
		this.y = Y;
		this.ML = new ArrayList<Integer>(); // 0 = UP 1 = RIGHT 2 = DOWN 3 = LEFT
		
	}
	
	public void printMap(node[][] N){
		
		for(int i=0; i<N.length; i++){
			String S = "";
			for(int j=0; j<N[i].length; j++){
				if(N[i][j].dist == Integer.MAX_VALUE){
					S = S + "X\t";
				} else {
					S = S + N[i][j].dist + "\t";
				}
			}
			System.out.println(S);
		}
		
	}

	@Override
	public int nextMove() {
		// TODO Auto-generated method stub
		return 0;
	}

	@Override
	public ArrayList<Integer> moveList() {
		return ML;
	}
	
		
	private class node{
		
		int[] prev;
		int x,y, dist;
		boolean inQ = true;
		
		node(int X, int Y){
			x = X;
			y = Y;
			prev = new int[2];
			prev[0] = -1;
			prev[1] = -1;
			dist = Integer.MAX_VALUE;
		}
		
	}
	
	private int distbetween(int from, int to){
		
		if (to == 1){				// Grass
			return 2;
		} else if (to == 3){		// Road
			return 1;
		} else {
			return Integer.MAX_VALUE;
		}
	}
	
	private boolean passable(int t){
		switch(t){
		case 0:
			return false;
		case 1:
			return true;
		case 2:
			return false;
		case 3:
			return true;
		case 4:
			return false;
		case 5:
			return true;
		case 6:
			return true;
		default:
			return false;
		}
		
	}
	
	public node[][] graph(){ 
		// Returns a 2d array of nodes corresponding to the shortest path via Djikstra's algorithm.
		
		int r = Settings.rows;
		int c = Settings.columns;
		
		node [][] path = new node [r][c];
		ArrayList<node> Q = new ArrayList<node>();
		
		for (int i=0; i<r; i++){
			for( int j=0; j<c; j++){
				path[i][j] = new node(i,j);
				Q.add(path[i][j]);
			}
		}
		
		path[x][y].dist = 0;
		
		while(Q.size() > 0){
			int minval = Integer.MAX_VALUE;
			int minind = 0;
			for(int i=0; i<Q.size(); i++){
				if (Q.get(i).dist < minval){
					minval = Q.get(i).dist;
					minind = i;
				}
			}
			
			if (minval == Integer.MAX_VALUE){
				break; // All remaining nodes are inaccessible.
			}
			
			int cx = Q.get(minind).x;
			int cy = Q.get(minind).y;
			
			Q.remove(minind);
			path[cx][cy].inQ = false;
			
			//int alt = Integer.MAX_VALUE;
			try{
				if (path[cx][cy + 1].inQ && passable(map[cx][cy + 1])){	// Upper neighbor
					int alt = path[cx][cy].dist + distbetween(map[cx][cy], map[cx][cy + 1]);
					if (alt < path[cx][cy + 1].dist){
						path[cx][cy + 1].dist = alt;
						path[cx][cy + 1].prev[0] = cx;
						path[cx][cy + 1].prev[1] = cy;
					}
				}
			}catch(ArrayIndexOutOfBoundsException e){}
			try{
				if (path[cx + 1][cy].inQ && passable(map[cx + 1][cy])){	// Right neighbor
					int alt = path[cx][cy].dist + distbetween(map[cx][cy], map[cx + 1][cy]);
					if (alt < path[cx + 1][cy].dist){
						path[cx + 1][cy].dist = alt;
						path[cx + 1][cy].prev[0] = cx;
						path[cx + 1][cy].prev[1] = cy;
					}
				}
			}catch(ArrayIndexOutOfBoundsException e){}
			try{
				if (path[cx][cy - 1].inQ && passable(map[cx][cy - 1])){	// Lower neighbor
					int alt = path[cx][cy].dist + distbetween(map[cx][cy], map[cx][cy - 1]);
					if (alt < path[cx][cy - 1].dist){
						path[cx][cy - 1].dist = alt;
						path[cx][cy - 1].prev[0] = cx;
						path[cx][cy - 1].prev[1] = cy;
					}
				}
			}catch(ArrayIndexOutOfBoundsException e){}
			try{
				if (path[cx - 1][cy].inQ && passable(map[cx - 1][cy])){	// Left neighbor
					int alt = path[cx][cy].dist + distbetween(map[cx][cy], map[cx - 1][cy]);
					if (alt < path[cx - 1][cy].dist){
						path[cx - 1][cy].dist = alt;
						path[cx - 1][cy].prev[0] = cx;
						path[cx - 1][cy].prev[1] = cy;
					}
				}
			}catch(ArrayIndexOutOfBoundsException e){}
			
		}
		
		return path;
		
	}
	/*	- Djikstra's Algorithm pseudocode from Wikipedia
	 1  function Dijkstra(Graph, source):
	 2      for each vertex v in Graph:            // Initializations
	 3          dist[v] := infinity ;              // Unknown distance function from source to v
	 4          previous[v] := undefined ;         // Previous node in optimal path from source
	 5      end for ;
	 6      dist[source] := 0 ;                    // Distance from source to source
	 7      Q := the set of all nodes in Graph ;   // All nodes in the graph are unoptimized - thus are in Q
	 8      while Q is not empty:                  // The main loop
	 9          u := vertex in Q with smallest distance in dist[] ;
	10          if dist[u] = infinity:
	11              break ;                        // all remaining vertices are inaccessible from source
	12          end if ;
	13          remove u from Q ;
	14          for each neighbor v of u:          // where v has not yet been removed from Q.
	15              alt := dist[u] + dist_between(u, v) ;
	16              if alt < dist[v]:              // Relax (u,v,a)
	17                  dist[v] := alt ;
	18                  previous[v] := u ;
	19                  decrease-key v in Q;       // Reorder v in the Queue
	20              end if ;
	21          end for ;
	22      end while ;
	23      return dist[] ;
	24  end Dijkstra.
	*/
	
	public node[][] find(int X, int Y){
		
		node [][] N = graph();
		if(N[X][Y].dist == Integer.MAX_VALUE){
			System.out.println("Node " + X + "," + Y + " is inaccessible from " + x + "," + y);
			
		} else if(X == x && Y == y) {
			System.out.println("WE HAVE ARRIVED");
		} else {
			N[X][Y].dist = 0;
			printMap(N);
			System.out.println("\n");
			N = find(N[X][Y].prev[0], N[X][Y].prev[1]);
			if (X == N[X][Y].prev[0]){
				if (Y == N[X][Y].prev[1] + 1){
					ML.add(1);
					System.out.println("Move Right");
				}else{
					ML.add(3);
					System.out.println("Move Left");
				}
			}else{ 
				if (X == N[X][Y].prev[0] + 1){
					ML.add(2);
					System.out.println("Move Down");
				}else{
					ML.add(0);
					System.out.println("Move Up");
				}
			}
		}
		return N;
			
		
		
	}
	

}
